//(c) Copyright 2012 Hewlett-Packard Development Company, L.P.
//
//Confidential computer software. Valid license from HP required for possession, use or copying.
//Consistent with FAR 12.211 and 12.212, Commercial Computer Software, Computer Software Documentation, 
//and Technical Data for Commercial Items are licensed to the U.S. Government under vendor's standard commercial license.

package com.algorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.TreeSet;

import junit.framework.Assert;

public class SortAlgorithms {

	/**
	 * 冒泡排序
	 * 比较数组相邻的两个值，把大的像泡泡一样“冒”到数组后面去，一共要执行N的平方除以2这么多次的比较和交换的操作（N为数组元素），
	 * <br> <br>
	 * 时间复杂度： Ο(n²)
	 * <br><br>
	 * 优点：稳定，简单，易理解
	 * <br>
	 * 缺点：慢
	 * 
	 * @param list
	 */
	public static int[] bubblerSort(int[] list) {
		int[] tempList = Arrays.copyOf(list, list.length);
		for (int i = 0; i < tempList.length; i++) {
			for (int j = 0; j < tempList.length - i - 1; j++) {
				if (tempList[j] > tempList[j + 1]) {
					swap(tempList, j, j + 1);
				}
			}
			//System.out.println("i=" + i + ",list:" + Arrays.toString(tempList));
		}
		return tempList;
	}

	/**
	 * 选择排序
	 * 找出最大的一个元素，和末尾的元素交换，然后再从头开始，查找第1个到第N-1个元素中最大的一个，和第N-1个元素交换,思路跟冒泡差不多，只是移动的元素比冒泡少，所以效率比冒泡高
	 * <br> <br>
	 * 时间复杂度： Ο(n²)
	 * <br><br>
	 * 优点：稳定，简单，易理解,比冒泡性能好
	 * <br>
	 * 缺点：慢
	 * 
	 * @param list
	 */
	public static int[] selectionSort(int[] list) {
		int[] tempList = Arrays.copyOf(list, list.length);
		int maxIndex = 0;
		for (int i = 0; i < tempList.length; i++) {
			maxIndex = 0;
			int l = tempList.length - i;
			for (int j = 0; j < l; j++) {
				if (tempList[j] > tempList[maxIndex]) {//查找最大元素
					maxIndex = j;
				}
			}
			if (maxIndex != l - 1) {
				swap(tempList, maxIndex, l - 1);//把最大元素与最后一个元素交换
			}
			//System.out.println("i=" + i + ",list:" + Arrays.toString(tempList));
		}
		return tempList;
	}

	/**
	 * 直接插入排序
	 * 从未排序的部分中取出一个元素，插入到已经排好序的部分去. 插入的位置从后往前找，这样可以使得如果数组本身是有序（顺序）的话，速度会非常之快
	 * <br> <br>
	 * 时间复杂度： 最佳效率O（n）；最糟效率O（n²）与冒泡、选择相同，
	 * <br><br>
	 * 优点：稳定，适用于已基本排序小列表 
	 * <br>
	 * 缺点：最糟情况跟冒泡一样慢
	 * 
	 * @param list
	 */
	public static int[] straightInsertionSort(int[] list) {
		int[] tempList = Arrays.copyOf(list, list.length);
		int t = 0;
		for (int i = 1; i < tempList.length; i++) {
			t = tempList[i]; //设t为未排序的第一个元素，从第2个元素开始
			int j = i - 1;
			while (j >= 0 && tempList[j] > t) {//将t与已排序元素从后往前比较，寻找t应插入的位置
				tempList[j + 1] = tempList[j]; //后移元素
				j--;
			}
			tempList[j + 1] = t;//后称完成后，插入t到指定位置
		}
		return tempList;
	}

	public static int[] quickSort(int[] list) {
		int[] tempList = Arrays.copyOf(list, list.length);
		quickSort(tempList, 0, tempList.length - 1);
		return tempList;

	}

	/**
	 * 	1．先从数列中取出一个数作为基准数。<br>
		2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。<br>
		3．再对左右区间重复第二步，直到各区间只有一个数。<br>
		 * <br> <br>
	 * 时间复杂度： 最佳效率O（n * lg *n）；最糟效率O（n²）与冒泡、选择相同，
	 * <br><br>
	 * 优点：适用于已基本排序小列表 
	 * <br>
	 * 缺点：不稳定，用了递归，如果数据量很大，大量的递归调用会导致性能下降
	 * 
	 * @param list
	 * @param low
	 * @param high
	 */
	public static void quickSort(int[] list, int low, int high) {
		int i = low, j = high, key = list[i];
		if (i < j) {
			while (i < j) {
				while (i < j && list[j] > key) {// 从右向左找第一个<=key的数  
					j--;
				}
				if (i < j) {
					list[i++] = list[j];
				}
				while (i < j && list[i] <= key) {//从左向右找第一个>key的数  
					i++;
				}
				if (i < j) {
					list[j--] = list[i];
				}
			}
			list[i] = key;
			quickSort(list, low, i - 1);//左侧排序
			quickSort(list, i + 1, high);//右侧排序
		}
	}

	/**
	 * 桶式排序是目前最快的排序，它只要通过2轮遍历：第1轮遍历待排数据，统计每个待排数据“落入”各桶中的个数，第2轮遍历buckets用于重新计算buckets中元素的值，
	 * 2轮遍历后就可以得到每个待排数据在有序序列中的位置，然后将各个数据项依次放入指定位置即可
	 * <br> <br>
	 * 时间复杂度： 最佳效率O（n）；
	 * <br><br>
	 * 优点：稳定，适用于数量小的整形数据排序
	 * <br>
	 * 缺点：限制多，空间占用大
	 * @param list
	 * @return
	 */
	public static int[] bucketSort(int[] list) {
		int[] bucket = new int[list.length];
		for (int i = 0; i < list.length; i++) {
			bucket[list[i]] = bucket[list[i]] + 1;
		}

		List<Integer> r = new ArrayList<Integer>();
		for (int i = 0; i < bucket.length; i++) {
			if (bucket[i] > 0) {
				for (int j = 0; j < bucket[i]; j++) {
					r.add(i);
				}
			}
		}
		int[] tempList = new int[r.size()];
		for (int i = 0; i < r.size(); i++) {
			tempList[i] = r.get(i);
		}
		return tempList;

	}

	public static int[] mergeSort(int[] list) {
		int[] tempList = Arrays.copyOf(list, list.length);
		tempList = sort(tempList);
		return tempList;
	}

	public static int[] sort(int[] a) {
		if (a.length <= 1)
			return a;
		if (a.length == 2) {
			if (a[0] > a[1]) {
				swap(a, 0, 1);
			}
			return a;
		}
		//System.out.println("left: " + Arrays.toString(getHalf(a, true)) + " ,right: " + Arrays.toString(getHalf(a, false)));
		int[] left = sort(getHalf(a, true));
		int[] right = sort(getHalf(a, false));
		return merge(left, right);

	}

	private static int[] merge(int[] left, int[] right) {
		int[] t = new int[left.length + right.length];
		int i = 0, j = 0, k = 0;
		while (i < left.length && j < right.length) {
			if (left[i] <= right[j]) {
				t[k++] = left[i++];
			} else {
				t[k++] = right[j++];
			}
		}

		while (i < left.length) {
			t[k++] = left[i++];
		}
		while (j < right.length) {
			t[k++] = right[j++];
		}

		return t;
	}

	private static int[] getHalf(int[] a, boolean isLeft) {
		int l = a.length / 2;
		if (a.length % 2 == 1 && isLeft) {//left
			l = l + 1;
		}
		int mid = l;
		int[] t = new int[l];
		if (a.length % 2 == 1 && !isLeft) {//right
			mid = mid + 1;
		}

		for (int i = 0; i < t.length; i++) {
			if (isLeft) {
				t[i] = a[i];
			} else {
				t[i] = a[i + mid];
			}
		}
		return t;
	}

	private static void swap(int[] list, int i, int j) {
		int t = list[i];
		list[i] = list[j];
		list[j] = t;
	}

	/**
	 * 二分查找
	 * @param list
	 * @param key
	 * @return
	 */
	public static int binarySearch(int[] list, int key) {
		int low = 0, high = list.length - 1, mid = (low + high) / 2;
		int r = -1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (key == list[mid]) {
				return mid;
			} else if (key < list[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return r;
	}

	public static void findLost() {
		//很多成对出现数字保存在磁盘文件中，注意成对的数字不一定是相邻的，如2, 3, 4, 3, 4, 2,现再因故少了一位,请找出
		int[] a = new int[] { 2, 3, 4, 3, 4 };
		int r = 0;
		for (int i = 0; i < a.length; i++) {
			r ^= a[i];//异或来完成,异或的特点:与自身相同为0,不同为1,而且满足交换律
		}
		System.out.println("The lost is:" + r);
	}

	/**
	 * 堆排序<br>
	 * 由于堆也是用数组模拟的，故堆化数组后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，
	 * 重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了
	 * <br>
	 * <br>
	 * 时间复杂度: O(n* log2 *n)
	 * <br>
	 * 不稳定
	 * @param list
	 * @return
	 */
	public static int[] heapSort(int[] list) {
		int[] tempList = Arrays.copyOf(list, list.length);
		buildHeap(tempList);
		for (int i = tempList.length - 1; i > 0; i--) {
			swap(tempList, i, 0);
			maxHeapify(tempList, 0, i);
		}
		return tempList;
	}

	public static void buildHeap(int[] list) {
		for (int i = list.length / 2 - 1; i >= 0; i--) {
			maxHeapify(list, i, list.length);
		}
	}

	public static void maxHeapify(int[] list, int i, int size) {
		int left = 2 * i + 1, right = left + 1, maxIdx = i;
		if (i <= size) {
			//这里默认建立最大堆,比较操作改成>时建最小堆
			if (left < size && list[maxIdx] < list[left]) {
				maxIdx = left;
			}
			if (right < size && list[maxIdx] < list[right]) {
				maxIdx = right;
			}
			if (maxIdx != i) {
				swap(list, maxIdx, i);
				maxHeapify(list, maxIdx, size);
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int[] list = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 4 };
		System.out.println("Original list is:" + Arrays.toString(list));

		String expected = "[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]";

		int[] r = bubblerSort(list);
		Assert.assertEquals("Incorrect output of bubblerSort", expected, Arrays.toString(r));

		r = selectionSort(list);
		Assert.assertEquals("Incorrect output of selectionSort", expected, Arrays.toString(r));

		r = straightInsertionSort(list);
		Assert.assertEquals("Incorrect output of straightInsertionSort", expected, Arrays.toString(r));

		r = quickSort(list);
		Assert.assertEquals("Incorrect output of quickSort", expected, Arrays.toString(r));

		r = bucketSort(list);
		Assert.assertEquals("Incorrect output of bucketSort", expected, Arrays.toString(r));

		r = mergeSort(list);
		System.out.println("After merge sorted:" + Arrays.toString(r));
		Assert.assertEquals("Incorrect output of mergeSort", expected, Arrays.toString(r));

		System.out.println("The index of 3 in the list is: " + binarySearch(r, 3));

		r = heapSort(list);
		System.out.println("After head sorted: " + Arrays.toString(r));
		Assert.assertEquals("Incorrect output of heapSort", expected, Arrays.toString(r));

		//Arrays.sort(list);
		//List<Integer> a = new ArrayList<Integer>();
		//Collections.sort(a);

		//int[]aa = new int[2147483647];

		TreeSet<Integer> t = new TreeSet<Integer>();
		t.add(1);
		t.add(0);
		t.add(3);
		t.remove(t.first());
		t.add(2);
		//System.out.println(t);

		Stack<Integer> s = new Stack<Integer>();
		s.push(1);
		int j = s.pop();
		System.out.println(j);

		System.out.println(3 ^ 4 ^ 4);

		findLost();
	}

}
